package algocasts;

public class P149_UniqueBinarySearchTrees {
    // Time: O(n^2)  Space: O(n)
    public int numTrees(int n) {
        if (n < 0) return 0;
        int[] d = new int[n + 1];
        d[0] = 1;
        for (int i = 0; i <= n; i++)
            for (int j = 1; j <= i; j++)
                d[i] += d[j - 1] * d[i - j];
        return d[n];
    }

    // Time: O(n)  Space: O(1)
    public int numTrees_Math(int n) {
        if (n < 0) return 0;
        long result = 1;
        for (int k = 1; k <= n; k++)
            result = result * (n + k) / k;
        return (int) (result / (n + 1));
    }

}
